Secret sharing (or threshold secret sharing) is a cryptographic scheme that divides a secret into n pieces (or shares) such that any k of them (k<n) can be used to reconstruct the secret.
Adi Shamir discloses a technique that uses polynomial interpolations in the finite field GF(p) to construct a threshold secret sharing scheme (A. Shamir, “How to Share a Secret,” Communications of the ACM, v. 24, n. 11, November 1979, pp. 612-613). George Blakley discloses a technique that uses hyperplane intersections in space to reconstruct a secret (G. R. Blakley, “Safeguarding Cryptographic Keys,” Proceedings of the National Computer Conference, 1979, American Federation of Information Processing Societies, c. 48, 1979, pp. 313-317). However, in the polynomial interpolation scheme, inadvertently using an extra share produces an incorrect result. In the hyperplane intersection scheme, the number of required shares is obvious, and there is no way to use too many. Thus, it is generally not possible to distribute shares without also informing the recipients how many shares are required to reconstruct the secret.
Other secret sharing techniques based on the Chinese remainder theorem, such as the Asmuth-Bloom algorithm (C. Asmuth and J. Bloom, “A Modular Approach to Key Safeguarding,” IEEE Transactions on Information Theory, v. IT-29, n. 2, March 1983, pp. 208-210), have also been proposed. However, these algorithms are defined only in the integer ring, which generally involve manipulation of integers of large sizes. Large integers are not suitable for computer operations. Thus, there is a need to develop a secret sharing technique that overcomes the above inherent limitations of the known techniques.